package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author: ZhouBert
 * @date: 2020/11/26
 * @description: 二叉树的中序遍历 https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
 */
public class B_94_二叉树的中序遍历 {

	/**
	 * 通过递归得出的算法
	 *
	 * @param root
	 * @return
	 */
	public List<Integer> inorderTraversalByRecursive(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		inorder(root, res);
		return res;
	}

	/**
	 * 左 - 根 - 右
	 *
	 * @param root
	 * @param list
	 */
	private void inorder(TreeNode root, List<Integer> list) {
		if (root.left != null) {
			inorder(root.left, list);
		}
		list.add(root.val);
		if (root.right != null) {
			inorder(root.right, list);
		}
	}

	/**
	 * 通过迭代解决中序遍历
	 *
	 * @param root
	 * @return
	 */
	public static List<Integer> inorderTraversalByIterator(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		Stack<TreeNode> stack = new Stack<>();
		TreeNode cur = root;
		//标记该节点是否已经被读过（对于 left == null 时无影响！）
		//其实 一旦 isNodeRead = true -> 该节点肯定是有 left 的
		boolean isNodeRead = false;
		while (cur.left != null || cur.right != null || !stack.isEmpty()) {
			if (cur.left != null && !isNodeRead) {
				//只要做节点不为空，就可以入栈
				//入栈待处理
				stack.push(cur);
				cur = cur.left;
				isNodeRead = false;
			} else if (cur.right != null) {
				//left == null && right != null
				//从栈弹出的节点，需要立即处理 + 判断右节点的
				res.add(cur.val);
				cur = cur.right;
				isNodeRead = false;
			} else {
				if (stack.isEmpty()) {
					//此时已经出栈的元素 && 只有一个左节点
					break;
				}
				//left == null && right == null
				res.add(cur.val);
				cur = stack.pop();
				//将弹出的节点的已读过的属性设置为 true
				isNodeRead = true;
			}
//			if (cur.left == null && cur.right == null) {
//				//来到了左底
//				res.add(cur.val);
//				cur = stack.pop();
//			}
		}
		res.add(cur.val);
		return res;
	}

	/**
	 * 通过迭代实现中序遍历
	 * 通过 一个标志位来判断
	 * @param root
	 * @return
	 */
	public static List<Integer> inorderTraversalByIterator2(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		//先找寻最左边的节点
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		TreeNode cur = root;
		//可以通过下一个节点来决定该标志位
		boolean readLeft = false;
		while (!stack.isEmpty()) {
			cur = stack.pop();
			while (cur.left != null && !readLeft) {
				stack.push(cur);
				cur = cur.left;
			}
			//直至最左的 左子节点
			res.add(cur.val);
			if (cur.right != null) {
				stack.push(cur.right);
				readLeft = false;
			}else {
				readLeft = true;
			}
		}
		return res;
	}

	public static void main(String[] args) {
		testInorder();

//		TreeNode root = new TreeNode(1);
//		root.right = new TreeNode(2);
//		root.right.left = new TreeNode(3);
//		inorderTraversalByIterator(root);
	}

	/**
	 * 测试中序遍历
	 */
	static void testInorder(){
		String str = "[1,null,2,3]";
		str = "[1,2]";
		TreeNode node = TreeNode.stringToTreeNode(str);
		List<Integer> list = inorderTraversalByIterator2(node);
		System.out.println("list = " + list);
	}
}
